//给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。 
//
// 例如，给出 n = 3，生成结果为： 
//
// [
//  "((()))",
//  "(()())",
//  "(())()",
//  "()(())",
//  "()()()"
//]
// 
// Related Topics 字符串 回溯算法
package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：括号生成
public class P22GenerateParentheses{
    public static void main(String[] args) {
        Solution solution = new P22GenerateParentheses().new Solution();
        // TO TEST
    }
    

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        generate("", result, n, n);
        return result;
    }

    // 递归实现--谷乐
    public void generate(String sublist, List<String> result, int left, int right) {
        if (right == 0 && left == 0) {
            result.add(sublist);
            return;
        }
        if (left > 0) {
            generate(sublist + "(", result, left - 1, right);
        }
        if (right > left) {
            generate(sublist + ")", result, left, right - 1);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
